#!/usr/bin/env python

import sys
import re
from collections import deque
from itertools import izip_longest, izip

#=======================================================================================================================

class ForppException(Exception):
    pass

#=======================================================================================================================

class ParseException(ForppException):
    pass

#=======================================================================================================================

class DefineMatch(object):
    
    def __init__(self, name, args, value):
        self._groupdict = {'name': name, 'args': args, 'value': value}
        
    def groupdict(self):
        return self._groupdict
    
    def group(self, name):
        return self._groupdict[name]

class DefineMatcher(object):
    
    def __init__(self):
        self._re = re.compile(r'^!#\s*DEFINE\s+(?P<name>[a-zA-Z_]+)\s*(?P<text>.*)$')
    
    def match(self, line):
        match = self._re.search(line)
        if not match:
            return None
        name = match.group('name')
        text = match.group('text').strip()
        if text.startswith('('):
            idx = 1
            depth = 1
            while depth:
                if text[idx] == ')': depth -= 1
                if text[idx] == '(': depth += 1
                idx += 1
            args = text[:idx]
            value = text[idx:]
        else:
            args = None
            value = text
        return DefineMatch(name, args, value)

class FunctionMatch(object):
    
    def __init__(self, name, args, start, length):
        self._groupdict = {'name': name, 'args': args}
        self._start = start
        self._end = start + length
        
    def groupdict(self):
        return self._groupdict
    
    def group(self, name):
        return self._groupdict[name]
    
    def start(self):
        return self._start
    
    def end(self):
        return self._end

class FunctionMatcher(object):
    
    def __init__(self, names):
        self._names = names
        self._re = re.compile(r'(\b|^)(?P<name>[a-zA-Z_][a-zA-Z_1-9]*)\s*(?P<text>.*)')
        
    def search(self, line):
        match = self._re.search(line)
        if not match:
            return None
        name = match.group('name')
        text = match.group('text').strip()
        if name not in self._names:
            return None
        if text.startswith('('):
            idx = 1
            depth = 1
            while depth:
                if text[idx] == ')': depth -= 1
                if text[idx] == '(': depth += 1
                idx += 1
            args = text[:idx]
            length = len(name) + idx
        else:
            args = None
            length = len(name)
        return FunctionMatch(name, args, match.start(), length)
        

FORPP_RE    = re.compile(r'^!#\s*(?P<command>\S+).*$')

END_RE      = re.compile(r'^!#\s*END\s+(?P<command>\S+)\s*$')
DEFINE_RE   = re.compile(r'^!#\s*DEFINE\s+(?P<name>[a-zA-Z_]+)\s*(?P<args>\(.*\))?(?P<value>.*)\s*$')
#DEFINE_RE   = DefineMatcher()
FOR_RE      = re.compile(r'^!#\s*FOR\s+(?P<var>\S+)\s+IN\s+(?P<list>.*)\s*$')
IF_RE       = re.compile(r'^!#\s*IF\s+(?P<test>.*)\s*$')
ELSEIF_RE   = re.compile(r'^!#\s*ELSE\s*IF\s+(?P<test>.*)\s*$')
ELSE_RE     = re.compile(r'^!#\s*ELSE\s*$')
SET_RE      = re.compile(r'^!#\s*SET\s+(?P<name>\S+)\s+(?P<value>.*)\s*$')
INCLUDE_RE  = re.compile(r'^!#\s*INCLUDE\s+(?P<file_name>\S+)\s*$')
APPEND_RE   = re.compile(r'^!#\s*APPEND\s+(?P<name>\S+)\s+(?P<value>.*)\s*$')

VAR_RE = re.compile(r'<(?P<name>[a-zA-Z_][a-zA-Z_1-9]*)(?P<expr>(?P<op>[\+-/\*])(?P<num>\d+))?>')
FUNCTION_RE = re.compile(r'(\b|^)([a-zA-Z_][a-zA-Z_1-9]*)(\([^)]*\)).*')

OP_MAP = {
    '+': int.__add__,
    '-': int.__sub__,
    '/': int.__div__,
    '*': int.__mul__,
}

#=======================================================================================================================

def split_args(arg_string):
    depth = 0
    idx = 0
    args = []
    buf = ''
    
    while idx < len(arg_string):
        char = arg_string[idx]
        if char == '(':
            depth += 1
            buf += char
        elif char == ')':
            depth -= 1
            buf += char
        elif char == ',' and depth == 0:
            args.append(buf)
            buf = ''
        else:
            buf += char
        idx += 1
    
    if buf:
        args.append(buf.strip())
        
    return args

#=======================================================================================================================

def parse_list(list_string):
    depth = 0
    idx = 0
    buf = ''
    lst = []
    
    list_string = list_string.strip()
    if list_string[0] == '[' and list_string[-1] == ']':
        list_string = list_string[1:-1]
    elif list_string[0] == '(' and list_string[-1] == ')':
        list_string = list_string[1:-1]
    else:
        raise ForppException('Invalid list %s' % list_string)
    
    while idx < len(list_string):
        char = list_string[idx]
        if char == '(':
            depth += 1
            buf += char
        elif char == ')':
            depth -= 1
            buf += char
        elif char == ',' and depth == 0:
            lst.append(buf.strip())
            buf = ''
        else:
            buf += char
        idx += 1
    
    if buf:
        lst.append(buf.strip())
    
    #idx = 0
    #while idx < len(lst):
    #    item = lst[idx]
    #    if (item[0] == '[' and item[-1] == ']') or (item[0] == '(' and item[-1] == ')'):
    #        lst[idx] = parse_list(item)
    #    idx += 1
    
    return lst

#=======================================================================================================================

class Parser(object):
    
    def __init__(self, caller):
        self._macros = {}
        self._tests = []
        self._test_blocks = []
        self._caller = caller
    
    def _parse_define(self):
        match = DEFINE_RE.match(self._block_definition)
        name = match.group('name')
        args = match.group('args')
        value = match.group('value')
        
        if value:
            lines = [value]
        else:
            lines = self._block_lines
        
        if args is not None:
            if not args:
                self._macros[name] = FunctionBlock(name, None, lines=lines, parent=self._caller)
            else:
                self._macros[name] = FunctionBlock(name, split_args(args), lines=lines, parent=self._caller)
        else:
            self._macros[name] = MacroBlock(name, lines=lines, parent=self._caller)
    
    def _parse_for(self):
        match = FOR_RE.match(self._block_definition)
        var = match.group('var')
        lst = match.group('list')
        return ForBlock(var, lst, lines=self._block_lines, parent=self._caller)
    
    def _parse_if(self):
        match = (IF_RE.match(self._block_definition)
                    or ELSEIF_RE.match(self._block_definition)
                    or ELSE_RE.match(self._block_definition))
        if 'test' in match.groupdict():
            test = match.group('test')
        else:
            test = None
        self._tests.append(test)
        self._test_blocks.append(self._block_lines)
        return IfBlock(self._tests, self._test_blocks, parent=self._caller)
        
    def _parse_elseif(self):
        match = IF_RE.match(self._block_definition) or ELSEIF_RE.match(self._block_definition)
        test = match.group('test')
        self._tests.append(test)
        self._test_blocks.append(self._block_lines)

    def _parse_set(self):
        match = SET_RE.match(self._block_definition)
        parent = self._caller
        while parent._parent is not None:
            parent = parent._parent
        name = match.group('name')
        value = match.group('value')
        lines = TextBlock([value], parent=self._caller).expand()
        parent._macros[name] = MacroBlock(name, lines=lines, parent=self._caller)
        
    def _parse_include(self):
        match = INCLUDE_RE.match(self._block_definition)
        file_name = match.group('file_name')
        lines = open(file_name).readlines()
        for line in lines[::-1]:
            self._lines.appendleft(line)
            
    def _parse_append(self):
        match = APPEND_RE.match(self._block_definition)
        name = match.group('name')
        value = match.group('value')
        parent = self._caller
        while parent._parent is not None:
            parent = parent._parent
        lst = parent._macros[name]
        if lst[-1] != ']':
            raise ForppException('Invalid list %s' % lst)
        if len(lst) > 2:
            lst = lst[:-1] + ', ' + value + lst[-1]
        else:
            lst = lst[:-1] + value + lst[-1]
        parent._macros[name] = MacroBlock(name, lines=[lst], parent=self._caller)
    
    METHOD_MAP = {
        'DEFINE': _parse_define,
        'FOR': _parse_for,
        'IF': _parse_if,
        'SET': _parse_set,
        'APPEND': _parse_append,
        'INCLUDE': _parse_include,
    }
    
    def _build_block(self, command):
        block = Parser.METHOD_MAP[command](self)
        if block:
            self._output.append(block)
        self._block_lines = []
        self._block_definition = None
    
    def _parse_block_line(self, line):
        match = FORPP_RE.match(line)
        
        if match:
            command = match.group('command')
            
            if command == 'END':
                end_command = END_RE.match(line).group('command')
                if end_command != self._block_types[-1]:
                    raise ForppException('Mismatched END expected %s, found %s' % (self._block_types[-1], end_command))
                self._block_types.pop()
                if not self._block_types:
                    self._build_block(end_command)
                else:
                    self._block_lines.append(line)
            elif command in ('ELSEIF', 'ELSE'):
                if self._block_types[-1] != 'IF':
                    raise ForppException('%s found not in IF block' % command)
                if len(self._block_types) > 1:
                    self._block_lines.append(line)
                else:
                    self._parse_elseif()
                    self._block_definition = line
                    self._block_lines = []
            else:
                if not self._is_single_line_command(line):
                    self._block_types.append(command)
                self._block_lines.append(line)
        else:
            self._block_lines.append(line)
    
    def _is_single_line_command(self, line):
        match = DEFINE_RE.match(line)
        if match and match.group('value'):
            return True
        if INCLUDE_RE.match(line) or SET_RE.match(line) or APPEND_RE.match(line):
            return True
        return False
    
    def _parse_line(self, line):
        match = FORPP_RE.match(line)
        
        if match:
            command = match.group('command')
            if command in ('END', 'ELSEIF', 'ELSE'):
                raise ForppException('Unexpected %s found' % command)
            if self._is_single_line_command(line):
                self._block_definition = line
                self._build_block(command)
            else:
                self._block_definition = line
                self._block_types.append(command)
        else:
            self._output.append(line)
    
    def parse(self, lines):

        self._output = []
        self._lines = deque(lines)
        self._block_lines = []
        self._block_types = deque()
        self._block_definition = None

        while self._lines:
            
            line = self._lines.popleft()
            
            if isinstance(line, TextBlock):
                self._output.append(line)
                continue
            
            while line.endswith('\\\n'):
                cont = self._lines.popleft().lstrip().lstrip('!').lstrip()
                line = line.rstrip('\\\n') + cont
                continue
            
            if self._block_types:
                self._parse_block_line(line)
            else:
                self._parse_line(line)
                
        if self._block_types:
            raise ForppException('Incomplete block %s found' % self._block_types[-1])
        
        return self._output

    @property
    def macros(self):
        return self._macros

#=======================================================================================================================

class TextBlock(object):
    Type = 'TEXT'
    
    def __init__(self, lines=None, macros=None, parent=None, file_name=None):
        if macros is None:
            macros = {}
        if parent is not None and not isinstance(parent, TextBlock):
            raise ForppException('Invalid parent %s' % parent)
        if lines is None:
            lines = []
        self._lines  = lines
        self._macros = macros
        self._parent = parent
        self._parser = Parser(self)
        if file_name:
            self._macros['FILE'] = TextBlock([file_name])
        
    def append_line(self, line):
        self._lines.append(line)
        
    def _parse(self):
        lines = self._parser.parse(self._lines)
        self._macros.update(self._parser.macros)
        return lines
    
    @property
    def macros(self):
        if self._parent:
            tmp = self._parent.macros.copy()
        else:
            tmp = {}
        tmp.update(self._macros)
        return tmp
    
    def expand(self):
        lines = self._parse()
        
        output = []
        queue = deque(lines)
        if 'LINE' not in self.macros:
            self._macros['LINE'] = CountBlock()
        
        try:
            while True:
                line = queue.popleft()
                self.macros['LINE'].inc()
                
                if isinstance(line, TextBlock):
                    for l in line.expand()[::-1]:
                        queue.appendleft(l)
                        self.macros['LINE'].dec()
                    continue
                
                var_match = VAR_RE.search(line)
                #function_match = FUNCTION_RE.search(line)
                names = [name for name, block in self.macros.iteritems() if isinstance(block, FunctionBlock)]
                function_match = FunctionMatcher(names).search(line)
                
                if function_match:
                    name = function_match.group('name')
                    args = function_match.group('args')
                    macro = self.macros[name]
                    arg_list = parse_list(args)
                    lines = macro.expand(arg_list)
                    if lines:
                        tmp = []
                        tmp.append(line[:function_match.start()] + lines[0])
                        tmp += lines[1:]
                        tmp[-1] += line[function_match.end():]
                        for l in tmp[::-1]:
                            queue.appendleft(l)
                            self.macros['LINE'].dec()
                elif var_match:
                    name = var_match.group('name')
                    if name in self.macros:
                        if var_match.group('expr'):
                            op = OP_MAP[var_match.group('op')]
                            num = int(var_match.group('num'))
                            macro = self.macros[name]
                            lines = macro.expand()
                            if len(lines) != 1:
                                raise ForppException()
                            lines = [str(op(int(lines[0]), num))]
                        else:
                            macro = self.macros[name]
                            lines = macro.expand()
                        if lines:
                            tmp = []
                            tmp.append(line[:var_match.start()] + lines[0])
                            tmp += lines[1:]
                            tmp[-1] += line[var_match.end():]
                            for l in tmp[::-1]:
                                queue.appendleft(l)
                                self.macros['LINE'].dec()
                    else:
                        print >> sys.stderr, 'Unknown macro <%s>' % name
                        output.append(line)
                else:
                    output.append(line)

        except IndexError:
            pass
        
        return output
    
    def __repr__(self):
        return 'TextBlock(%s)' % self._lines

#=======================================================================================================================

class MacroBlock(TextBlock):
    Type = 'DEFINE'
    
    def __init__(self, name, **kwargs):
        TextBlock.__init__(self, **kwargs)
        self.name = name
            
    def __repr__(self):
        return 'MacroBlock(%s)' % (self.name)
    
#=======================================================================================================================

class CountBlock(TextBlock):
    Type = None
    
    def __init__(self, value=0):
        TextBlock.__init__(self)
        self.value = value
        
    def expand(self):
        return [str(self.value)]
    
    def __repr__(self):
        return 'Count(%d)' % self.value
    
    def inc(self):
        self.value += 1
        
    def dec(self):
        self.value -= 1
        
    def __repr__(self):
        return 'CountBlock(%d)' % self.value

#=======================================================================================================================

class ForBlock(TextBlock):
    Type = 'FOR'
    
    def __init__(self, var, for_list, **kwargs):
        TextBlock.__init__(self, **kwargs)
        self.var = var.strip()
        lines = TextBlock([for_list], parent=self).expand()
        if len(lines) != 1:
            raise ForppException('Invalid FOR list %s' % lst)
        self._list = parse_list(lines[0])
    
    def expand(self):
        output = []

        for val in self._list:
            self._macros[self.var] = TextBlock([val], parent=self)
            
            lines = self._parse()
            output += TextBlock.expand(self)
            
        return output
    
    def __repr__(self):
        return 'ForBlock(%s, %s)' % (self.var, self._list)

#=======================================================================================================================

class IfBlock(TextBlock):
    Type = 'IF'
    
    Comparators = {
        '==': lambda lhs, rhs: lhs == rhs,
        '!=': lambda lhs, rhs: lhs != rhs,
        '>' : lambda lhs, rhs: lhs > rhs,
        '>=': lambda lhs, rhs: lhs >= rhs,
        '<' : lambda lhs, rhs: lhs < rhs,
        '<=': lambda lhs, rhs: lhs <= rhs,
    }
    
    def __init__(self, tests, test_blocks, **kwargs):
        if len(tests) != len(test_blocks):
            raise ForppException('Invalid IF tests %s %s' % (tests, test_blocks))
        TextBlock.__init__(self, **kwargs)
        self._tests = tests
        self._test_lines = {}
        for test, block in izip(tests, test_blocks):
            self._test_lines[test] = block
        
    def expand(self):
        for test in self._tests:
            if test is None or self.eval_test(test):
                lines = self._test_lines[test]
                return TextBlock(lines, parent=self).expand()
            
    def eval_test(self, test):
        lines = TextBlock([test], parent=self).expand()
        if len(lines) != 1:
            raise ForppException()
        test = lines[0]
        
        for comparator, func in IfBlock.Comparators.iteritems():
            cmp_re = re.compile(r'^\s*(\d+)\s*%s\s*(\d+)\s*$' % comparator)
            match = cmp_re.match(test)
            if match:
                lhs = int(match.group(1))
                rhs = int(match.group(2))
                return func(lhs, rhs)
        
        raise ForppException(test)
    
    def __repr__(self):
        return 'IfBlock(%s, %s)' % (self._tests, [self._test_lines[test] for test in self._tests])

#=======================================================================================================================

class FunctionBlock(TextBlock):
    Type = 'DEFINE'
    
    def __init__(self, name, args, **kwargs):
        TextBlock.__init__(self, **kwargs)
        self.name = name.strip()
        if args:
            self.args = [a.strip() for a in args]
        else:
            self.args = []
        
    def expand(self, arg_vals):
        for name, val in izip_longest(self.args, arg_vals):
            self._macros[name] = MacroBlock(name, lines=[val], parent=self)
        return TextBlock.expand(self)
    
    def __repr__(self):
        return 'FunctionBlock(%s, %s)' % (self.name, self.args)

#=======================================================================================================================

if __name__ == '__main__':
    file_name = sys.argv[1]
    lines = open(file_name).readlines()
    block = TextBlock(lines, file_name=file_name)
    res = block.expand()
    for line in res:
        print line,